A point cloud is a set of vertices in a three-dimensional coordinate system, which is often created by three-dimensional scanners, such as LIDAR (Light Detection And Ranging) systems that measure a large number of points on the surface of an object, and output the point cloud as a data file. The point cloud is a collection of three-dimensional spatial points, representing the visible surface of the object that has been scanned or digitized. For example in FIG. 1, a scatter plot of point cloud data from the scan of the “Happy Buddha” includes 543,652 points in the point cloud, which may cause storage and transmission of such huge data problematic.
Currently, the method of compressing a three-dimensional point cloud is based on reconstructing a surface that fits the point cloud. The computation is on a regular rectangular grid, and the grid points are converted from three-dimensional to two-dimensional tiles. Furthermore, JPEG compression is used to save the information of the two-dimensional tiles. The key to obtain good compression is to compute the levelset function on a tube near the zero interface, and all values outside the tube are considered constant. Namely, most two-dimensional tiled data are constant and can be compressed well using JPEG.
The shrinkwrap algorithm is commonly used to reconstruct the surface on larger objects such as buildings and general terrain, however, it may be difficult to capture some detailed objects, such as power lines, traffic lights and especially trees due to missing areas or areas of low density in the point cloud data. In order to fill in these missing areas, a larger outer contour has to be taken as an initial surface, and the surface shrinks toward the points. As to trees, a large outer contour is formed around the tree and then shrinks toward the leaves, however, the trunk area does not usually resolve well, as the surface gets stuck between the ground and the leaves. Taking a smaller outer contour as the initial guess would solve the problem at the trunk area, but the problem of missing areas elsewhere may arise. In addition to trees, power lines generally have very sparse data points, and the shrinkwrap process usually cannot resolve them.
There are several advantages to use the shrinkwrap algorithm to reconstruct the surface represented by point cloud data, including denoising, path planning, and visibility calculations. However, some users may be more interested in preserving small details. Therefore, there remains a need for a new and improved method and apparatus for compressing three-dimensional point cloud data while preserving the details thereof.